﻿using System;
using System.Drawing.Imaging;
using System.Drawing;

namespace image
{
    /// <summary>
    /// ------------------------------------------------------------
    ///
    /// This implementation correctly handles duplicate points, and
    /// multiple points with the same x-coordinate.
    ///
    /// 1. Sort the points lexicographically by increasing (x,y), thus 
    ///    finding also a leftmost point L and a rightmost point R.
    /// 2. Partition the point set into two lists, upper and lower, according as 
    ///    point is above or below the segment LR.  The upper list begins with 
    ///    L and ends with R; the lower list begins with R and ends with L.
    /// 3. Traverse the point lists clockwise, eliminating all but the extreme
    ///    points (thus eliminating also duplicate points).
    /// 4. Eliminate L from lower and R from upper, if necessary.
    /// 5. Join the point lists (in clockwise order) in an array.
    /// </summary>
    public class Convexhull
    {
        public static Point[] ConvexHull(Point[] _aPoint)
        {
            // Sort points lexicographically by increasing (x, y)
            int N = _aPoint.Length;
            if (N <= 1)
            {
                return _aPoint;
            }
            Polysort.Quicksort(_aPoint);
            Point left = _aPoint[0];
            Point right = _aPoint[N - 1];
            // Partition into lower hull and upper hull
            CircularDoublyLinkedList lower = new CircularDoublyLinkedList(left), upper = new CircularDoublyLinkedList(left);
            for (int i = 0; i < N; i++)
            {
                double det = Point.Area2(left, right, _aPoint[i]);
                if (det > 0)
                {
                    upper = upper.Append(new CircularDoublyLinkedList(_aPoint[i]));
                }
                else if (det < 0)
                {
                    lower = lower.Prepend(new CircularDoublyLinkedList(_aPoint[i]));
                }
            }
            lower = lower.Prepend(new CircularDoublyLinkedList(right));
            upper = upper.Append(new CircularDoublyLinkedList(right)).Next;
            // Eliminate points not on the hull
            Eliminate(lower);
            Eliminate(upper);
            // Eliminate duplicate endpoints
            if (lower.Prev.m_Point.Equals(upper.m_Point))
            {
                lower.Prev.Delete();
            }
            if (upper.Prev.m_Point.Equals(lower.m_Point))
            {
                upper.Prev.Delete();
            }
            // Join the lower and upper hull
            Point[] res = new Point[lower.Size() + upper.Size()];
            lower.CopyInto(res, 0);
            upper.CopyInto(res, lower.Size());
            return res;

        }

        /// <summary>
        /// Eliminates the specified start.
        /// Graham's scan
        /// </summary>
        /// <param name="start">The start.</param>
        private static void Eliminate(CircularDoublyLinkedList start)
        {
            CircularDoublyLinkedList circularDoublyLinkedList = start, w = start.Prev;
            bool fwd = false;
            while (circularDoublyLinkedList.Next != start || !fwd)
            {
                if (circularDoublyLinkedList.Next == w)
                {
                    fwd = true;
                }
                if (Point.Area2(circularDoublyLinkedList.m_Point, circularDoublyLinkedList.Next.m_Point, circularDoublyLinkedList.Next.Next.m_Point) < 0) // right turn
                {
                    circularDoublyLinkedList = circularDoublyLinkedList.Next;
                }
                else
                {                                       // left turn or straight
                    circularDoublyLinkedList.Next.Delete();
                    circularDoublyLinkedList = circularDoublyLinkedList.Prev;
                }
            }
        }
    }



    /// <summary>
    /// ------------------------------------------------------------
    /// Points in the plane
    /// </summary>
    public class Point : Ordered
    {
        private static readonly Random rnd = new Random();

        private double x, y;

        /// <summary>
        /// Gets or sets the X.
        /// </summary>
        /// <value>The X.</value>
        public int X
        {
            get { return (int)x; }
            set { x = (double)value; }
        }

        /// <summary>
        /// Gets or sets the Y.
        /// </summary>
        /// <value>The Y.</value>
        public int Y
        {
            get { return (int)y; }
            set { y = (double)value; }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Point"/> class.
        /// </summary>
        /// <param name="x">The x.</param>
        /// <param name="y">The y.</param>
        public Point(double x, double y)
        {
            this.x = x; this.y = y;
        }

        /// <summary>
        /// Returns a <see cref="System.String"/> that represents this instance.
        /// </summary>
        /// <returns>
        /// A <see cref="System.String"/> that represents this instance.
        /// </returns>
        public override string ToString()
        {
            return "(" + x + ", " + y + ")";
        }

        /// <summary>
        /// Randoms the specified w.
        /// </summary>
        /// <param name="w">The w.</param>
        /// <param name="h">The h.</param>
        /// <returns></returns>
        public static Point Random(int w, int h)
        {
            return new Point(rnd.Next(w), rnd.Next(h));
        }

        /// <summary>
        /// Equalses the specified p2.
        /// </summary>
        /// <param name="p2">The p2.</param>
        /// <returns></returns>
        public bool Equals(Point p2)
        {
            return x == p2.x && y == p2.y;
        }

        /// <summary>
        /// Lesses the specified o2.
        /// </summary>
        /// <param name="o2">The o2.</param>
        /// <returns></returns>
        public override bool Less(Ordered o2)
        {
            Point p2 = (Point)o2;
            return x < p2.x || x == p2.x && y < p2.y;
        }

        /// <summary>
        /// Twice the signed area of the triangle (p0, p1, p2)
        /// </summary>
        /// <param name="p0"></param>
        /// <param name="p1"></param>
        /// <param name="p2"></param>
        /// <returns></returns>
        public static double Area2(Point p0, Point p1, Point p2)
        {
            return p0.x * (p1.y - p2.y) + p1.x * (p2.y - p0.y) + p2.x * (p0.y - p1.y);
        }
    }

    // ------------------------------------------------------------


    /// <summary>
    /// Circular doubly linked lists of Point
    /// </summary>
    public class CircularDoublyLinkedList
    {
        private CircularDoublyLinkedList m_Prev, m_Next;     // not null, except in deleted elements
        public Point m_Point;

        /// <summary>
        /// A new CDLL node is a one-element circular list
        /// </summary>
        /// <param name="val"></param>
        public CircularDoublyLinkedList(Point val)
        {
            this.m_Point = val; m_Next = m_Prev = this;
        }

        /// <summary>
        /// Gets the prev.
        /// </summary>
        /// <value>The prev.</value>
        public CircularDoublyLinkedList Prev
        {
            get { return m_Prev; }
        }

        /// <summary>
        /// Gets the next.
        /// </summary>
        /// <value>The next.</value>
        public CircularDoublyLinkedList Next
        {
            get { return m_Next; }
        }

        // Delete: adjust the remaining elements, make this one point nowhere
        public void Delete()
        {
            m_Next.m_Prev = m_Prev; m_Prev.m_Next = m_Next;
            m_Next = m_Prev = null;
        }

        /// <summary>
        /// Prepends the specified element.
        /// </summary>
        /// <param name="element">The element.</param>
        /// <returns></returns>
        public CircularDoublyLinkedList Prepend(CircularDoublyLinkedList element)
        {
            element.m_Next = this; element.m_Prev = m_Prev; m_Prev.m_Next = element; m_Prev = element;
            return element;
        }

        /// <summary>
        /// Appends the specified elt.
        /// </summary>
        /// <param name="elt">The elt.</param>
        /// <returns></returns>
        public CircularDoublyLinkedList Append(CircularDoublyLinkedList elt)
        {
            elt.m_Prev = this; elt.m_Next = m_Next; m_Next.m_Prev = elt; m_Next = elt;
            return elt;
        }

        /// <summary>
        /// Sizes this instance.
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            int count = 0;
            CircularDoublyLinkedList node = this;
            do
            {
                count++;
                node = node.m_Next;
            } while (node != this);
            return count;
        }

        /// <summary>
        /// Prints the FWD.
        /// </summary>
        public void PrintFwd()
        {
            CircularDoublyLinkedList node = this;
            do
            {
                Console.WriteLine(node.m_Point);
                node = node.m_Next;
            } while (node != this);
            Console.WriteLine();
        }

        /// <summary>
        /// Copies the into.
        /// </summary>
        /// <param name="_aValue">The _a value.</param>
        /// <param name="i">The i.</param>
        public void CopyInto(Point[] _aValue, int i)
        {
            CircularDoublyLinkedList node = this;
            do
            {
                _aValue[i++] = node.m_Point;	// still, implicit checkcasts at runtime 
                node = node.m_Next;
            } while (node != this);
        }
    }

    // ------------------------------------------------------------

    /// <summary>
    /// 
    /// </summary>
    public class Polysort
    {
        /// <summary>
        /// Swaps the specified arr.
        /// </summary>
        /// <param name="arr">The arr.</param>
        /// <param name="s">The s.</param>
        /// <param name="t">The t.</param>
        private static void Swap(Point[] arr, int s, int t)
        {
            Point tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
        }

        /// <summary>
        /// Swaps the specified arr.
        /// </summary>
        /// <param name="arr">The arr.</param>
        /// <param name="s">The s.</param>
        /// <param name="t">The t.</param>
        private static void Swap(Ordered[] arr, int s, int t)
        {
            Ordered tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
        }


        // Typed OO-style quicksort a la Hoare/Wirth

        /// <summary>
        /// Qsorts the specified arr.
        /// </summary>
        /// <param name="arr">The arr.</param>
        /// <param name="a">A.</param>
        /// <param name="b">The b.</param>
        private static void QSort(Ordered[] arr, int a, int b)
        {
            // sort arr[a..b]
            if (a < b)
            {
                int i = a, j = b;
                Point x = (Point)(arr[(i + j) / 2]);
                do
                {
                    while (arr[i].Less(x)) i++;
                    while (x.Less(arr[j])) j--;
                    if (i <= j)
                    {
                        Swap(arr, i, j);
                        i++; j--;
                    }
                } while (i <= j);
                QSort(arr, a, j);
                QSort(arr, i, b);
            }
        }

        /// <summary>
        /// Quicksorts the specified arr.
        /// </summary>
        /// <param name="arr">The arr.</param>
        public static void Quicksort(Ordered[] arr)
        {
            QSort(arr, 0, arr.Length - 1);
        }
    }

    /// <summary>
    /// 
    /// </summary>
    public abstract class Ordered
    {
        /// <summary>
        /// Lesses the specified that.
        /// </summary>
        /// <param name="that">The that.</param>
        /// <returns></returns>
        public abstract bool Less(Ordered that);
    }

    // ------------------------------------------------------------

    /*class TestCH {
      static void Main(string[] args) {
        if (args.Length == 1) {
          int N = int.Parse(args[0]);
          Point[] pts = new Point[N];
          for (int i=0; i<N; i++)
            pts[i] = Point.Random(500, 500);
          Point[] chpts = Convexhull.convexhull(pts);
          Console.WriteLine("Area is " + area(chpts));
          print(chpts);
        } else
          Console.WriteLine("Usage: TestCH <pointcount>\n");
      }

      // The centroid of a point set
      public static Point centroid(Point[] pts) { 
        int N = pts.Length;
        double sumx = 0, sumy = 0;
        for (int i=0; i<N; i++) {
          sumx += pts[i].x;
          sumy += pts[i].y;
        }
        return new Point(sumx/N, sumy/N);
      }

      // The area of a polygon (represented by an array of ordered vertices)
      public static double area(Point[] pts) { 
        int N = pts.Length;
        Point centr = centroid(pts);
        double area2 = 0;
        for (int i=0; i<N; i++) 
          area2 += Point.Area2(centr, pts[i], pts[(i+1)%N]);
        return Math.Abs(area2/2);
      }

      public static void print(Point[] pts) {
        int N = pts.Length;
        for (int i=0; i<N; i++) 
          Console.WriteLine(pts[i]);
      }
    }*/

}